#pragma once

#include <algorithm>
#include <vector>

namespace solution_016
{

class Solution
{
public:
    int threeSumClosest(std::vector<int>& nums, int target)
    {
        std::sort(nums.begin(), nums.end());

        int last_sum = nums[0] + nums[1] + nums[2];
        if (last_sum >= target)
            return last_sum;
        int min_dist = std::abs(last_sum - target);

        for (int k = 0, n = nums.size(); k + 2 < n; ++k) {
            if (k > 0 && nums[k] == nums[k-1])
                continue;
            for (int i = k + 1, j = n - 1; i < j; ) {
                int sum = nums[k] + nums[i] + nums[j];
                int dist = std::abs(sum - target);
                if (dist < min_dist) {
                    min_dist = dist;
                    last_sum = sum;
                }
                if (last_sum == target)
                    break;
                else if (sum < target)
                    while (++i < j && nums[i] == nums[i-1]);
                else
                    while (i < --j && nums[j] == nums[j+1]);
            }
        }
        return last_sum;
    }
};

}  /* namespace solution_016 */
